オイラーの定理とカーマイケルの定理

以前の記事, エルガマル暗号では, エルガマル暗号に関する諸々の前提の説明と, その実装について示した. 同エントリ内で, フェルマーの小定理¹については取り扱ったものの, その一般形であるオイラーの定理およびカーマイケルの定理について特に触れなかったため, 本エントリでそれらに関してまとめる. しばしば値の確認には, 簡単のため Haskell を使う.

オイラーの定理

いま, フェルマーテストを定義したとき, $FT_n(a)$ をパスするには(すなわち, フェルマーの小定理が示す合同式が成り立つには), 要件として, 既約剰余類郡 $\mathbb{Z}^{\ast}_n$ の各要素と $^\exists a\ \in\mathbb{Z}$ の積が全て異なり, $\bmod n$ の既約代表系のすべての積と合同でなければならない. たとえば, 法による合同関係で構成する剰余類の完全代表系²は $0,1,2,3,4,5,6,7$ であるが, $a=2$ としてしまうと, 既約剰余類郡が構成できていないので, 次のようにしても完全代表系が得られない(積をわざわざ示していないが, 非合同でないことは, 各要素の積が全て異なっていない時点で明白である).

Prelude> [x * 2 `rem` 8 | x <- [0..7]]
[0,2,4,6,0,2,4,6]

そこで, 先に述べた剰余類の既約代表系を考える. これは $\phi(8)=4$ 個³で, である. これを同じように, $\left\{1\cdot a,\ 3\cdot a,\ 5\cdot a,\ 7\cdot a\right\}$ とし, 先の要件を確認すると, この補題2より, で全体として $\left\{1,3,5,7\right\}$ と一致していて,

$1\cdot 3\cdot 5\cdot 7\equiv 1\cdot 3\cdot 5\cdot 7\cdot a^4\pmod{8}\label{eq:first}\tag{1}$

$\gcd(1\cdot 3\cdot 5\cdot 7,8)=1$ だから,

$1\cdot 3\cdot 5\cdot 7$ を約して,

$a^4\equiv 1\pmod{8}\label{eq:second}\tag{2}$ これは,

$\gcd(a,n)=1$ ということの他に,

$a$ および

$n$ の値に依存した論ではない. すなわち,

オイラーの定理

$a^{\phi(n)}\equiv 1\pmod{n}\ \left(2\leq n\in\mathbb{Z}^{+},\ \gcd(a,n)=1\right)$

がいえる⁴.

*Main> euler'sTheorem n = [a `modExp` (totient n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ euler'sTheorem 8
True

$n$ が素数 $p$ であるとき, $\phi(p)=p-1$ で, フェルマーの小定理¹となる⁵.

ラグランジュの定理

いま述べたオイラーの定理は, ラグランジュの定理を使っても証明できる. ラグランジュの定理は,

ラグランジュの定理

有限郡

$G$ の部分郡

$H$ の位数

$\mid H\mid$ は,

$G$ の位数

$\mid G\mid$ の約数となる.

$\mid G\mid\ =\ \mid G:H\mid \mid H\mid$

である.

証明: 有限郡 $G$ の部分郡 $H$ による類別が $\displaystyle G=\bigcup_i^r a_iH$ であるとき, $\mid G\mid=r\mid H\mid$ といえる. この $r$ は $r=\mid G:H\mid$ そのものなので, $\mid G\mid\ =\ \mid G:H\mid\mid H\mid$ . $\square$

ごく直感的な定理である. これを使えば, オイラーの定理は次のように証明できる.

補題1: 有限郡 $G$ とその元 $^\forall g\in G$ に対し, $g^{\mid G\mid}=e$ . $e\in G$ は単位元.

証明: 巡回部分郡 $H=\lt g\gt$ の元 $g$ の位数 $\mid H\mid$ は, 巡回して $g^i=e$ となる最小の $i\in\mathbb{N}$ であるといえる. すなわち

$g^{\mid H\mid}=e$ ここで, 商集合の位数を両辺に次のように与える.

$\left(g^{\mid H\mid}\right)^{\mid G:H\mid}=(e)^{\mid G:H\mid}$ 左辺は指数法則により, また右辺は単位元の繰り返しだから, これを次のようにかける.

$g^{\mid H\mid\mid G:H\mid}=e$ ラグランジュの定理より

$g^{\mid G\mid}=e$

$\square$

オイラーの定理の証明: オイラーの定理を仮定したとき, 脚注²より剰余類 $\overline{a}$ は法 $n$ に関する既約剰余類郡 $\mathbb{Z}^{\ast}_{n}$ に含まれる. $\mid\mathbb{Z}^{\ast}_{n}\mid=\phi(n)$ だから補題 1 より $\overline{a}^{\phi(n)}=\overline{a^{\phi(n)}}=\overline{1}$ . $\square$

カーマイケルの定理

オイラーの定理で用いる $\phi$ 関数は, $a^{m}\equiv 1\pmod{n}\ (m\in{N}, \gcd(a,n)=1$ を成立させる最小の整数 $m$ を持ち得ない. たとえば, $n=8$ では, 先の通り確かに $m=\phi(8)=4$ で合同式が満足できたが, $m=2$ としても, これを満足できる.

*Main> all (==1) $ take 100 $ [a `modExp` 2 $ 8 | a <- [2..], gcd a 8 == 1]
True

カーマイケルの $\lambda$ 関数は, 与えられた整数 $n$ に対して同合同式を満足する最小の $m$ を定義より自明に与える.

カーマイケルの

$\lambda$ 関数

扱う文字を全て整数とし,

$\lambda(n)$ は

$\begin{array}{lcl} \DeclareMathOperator{\lcm}{lcm} \lambda(1)&:=&1\\ \lambda(2)&:=&1\\ \lambda(4)&:=&4\\ \lambda(2^k)&:=&\phi(2^k)\ \left(0\leq k\leq 2\right)\\ \lambda(2^k)&:=&2^{k-2}=\dfrac{\phi(2^k)}{2}\ \left(e\geq 3\right)\\ \lambda(p^h)&:=&\phi(p^h)=(p-1)\cdot p^{h-1}\ \left(p\ is\ an\ odd\ prime, h\geq 1\right)\\ \lambda\left(2^kp_1^{h_1}p_2^{h_2}p_3^{h_3}\cdots p_t^{h_t}\right)&:=&\lcm\left(\lambda(2^k),\lambda(p_1^{h_1}),\lambda(p_2^{h_2}),\lambda(p_3^{h_3}),\cdots,\lambda(p_t^{h_t})\right)\ \left(p_n\ is\ an\ odd\ prime, k\geq 0, h_n\geq 1\right) \end{array}$ と定義する.

カーマイケルの定理

$a^{\lambda(n)}\equiv 1\pmod{n}\ (2\leq n\in\mathbb{Z}^{+},\ \gcd(a,n)=1)$

実装して確かめよう.

*Main> let carmichael'sLambda n = head [k | k <- [1..], and [(m `modExp` k $ n) < 2 | m <- [1..n] gcd m n < 2]]
*Main> let carmichael'sTheorem n = [a `modExp` (carmichael'sLambda n) $ n | a <- [2..], gcd a n == 1]
*Main> all (==1) $ take 100 $ carmichael'sTheorem 8
True

証明: フェルマーの小定理 ↩↩
補足. 郡 $G$ とその部分郡 $H$ があるとき, $H$ は郡であるから単位元 $e\in H$ を含む. よって, $^\exists a\in G$ の剰余類を $aH=\left\{ah\mid h\in H\right\}$ としたとき(簡単のため, 左剰余類として式をおいたが, これに深い意味はない.), $a=ae\in aH$ より $a\in aH$ である. この $a$ を剰余類の代表という. また郡は, 異なる $a_i$ を代表とした剰余類 $a_iH$ によって類別できる( $\displaystyle G=\bigcup_i a_iH$ ). この $\mid G:H\mid$ 個の類別に対して, 各剰余類から代表の元を取り, 構成した集合を, $G$ の $H$ に対する代表系という. ↩↩
ここで, $\phi$ は, オイラーのトーシェント関数. ↩
コード内のtotientとmodExpは, それぞれ以前の投稿のうち, オイラーのトーシェント関数の実装部分と, カーマイケル数を得るための実装を利用. ↩
この補足は冗長的かもしれないが, が素数である場合, $\mathbb{Z}_p^{\ast}$ が構成されるから, これから取った代表は素数と互いに素であることから, 既約代表である. この事実も, 一般に $\eqref{eq:first}$ から $\eqref{eq:second}$ へのような式変形が実行できることとの整合を示す. ↩

👋New blog information / ブログ移転のお知らせ